The present invention relates to a system for searching a digital image database to identify a set of images that bear a similarity to a first digital image of interest and for permitting a user at a remote terminal connected to a main computer by way of a limited bandwidth communicative link to efficiently obtain representations of the identified images.
With the advent of widespread computer technology and the formation of large databases of digital imagery, the ability to search through a database to find images of interest is becoming increasingly important. A number of approaches have been taken to address this problem.
Tal, U.S. Pat. No. 4,975,969, discloses a system for identifying peoples' faces. The system works by forming a ratio between two facial parameters, such as the distance between eyes and the tip of the nose and the distance between the tip of the nose and the bottom of the upper lip. This system is narrowly drawn toward the recognition of unique facial features and does not shed much light on the problem of finding particular digital images of interest from a more generalized database of digital images that includes many images that are not human faces.
Bradley, U.S. Pat. No. 4,991,223, discloses a system for recognizing image features using color elements. The image is scanned and each color in the image is represented by a code. Then the scanned and coded image is processed by a correlator which detects color discontinuities and thereby identifies differently colored features. This system is designed for use in inspection systems, in which a great deal of prior information is available and is not applicable to digital image database search systems, in which a great deal of search query formation flexibility is required.
Agrawal et al., U.S. Pat. No. 5,647,058, discloses a method for high-dimensionality indexing in a multi-media database. In this method a series of vectors are extracted from the objects in a database and used in a similarity search with a target object. A secondary search is performed to eliminate false positives.
Arman et al., U.S. Pat. No. 5,521,841, disclose a system for browsing the contents of a given video sequence. Representative frames are chosen from the video sequence. Each representative frame is abstracted into a group of 16.times.16 pixel blocks and compared with a similarly abstracted representation of a frame for which the user is attempting to find a match. Representative frames with a degree of similarity above a threshold are presented to the user for further inspection.
Barber et al., U.S. Pat. No. 5,579,471, disclose a method for searching an image databased on a query that is compiled by a human user by selecting image characteristics, such as color, from a display on a screen and for example, indicating where in the sought after image the color should occur. Using the user compiled query the computer system searches through the database and returns images which fall within some threshold of nearness to the query. No system is described by Barber et al. for abstracting complex shapes. This patent does, however, reference G. Taubin and D. B. Cooper "Recognition and Positioning of Rigid Objects Using Algebraic Moment Invariants," Geometric Methods in Computer Vision, SPIE Vol. 1570, pp 175-186, 1992. Barber et al., also disclose providing a set of images determined to be similar to the search image. There is, however, in this patent no preabstraction of the digital image database nor shape abstraction based on point saliency.
Coincidentally, with the development of object based programming, scenes may be digitally represented as a set of data objects. For example, a scene with a horse-drawn carriage crossing a bridge may be divided into a data object representing the carriage, another data object representing the horse pulling the carriage, and yet another data object representing the static imagery in the scene. This technique of scene representation increases the importance of shape recognition for searching through an image database, because a data object representation may have a distinctive, and therefore recognizable, shape.
One problem encountered by those linked to an image database by means of a standard telephone line or other narrow bandwidth link is the slow download time for detailed images. This may present a problem in searching through the digital image database because if, for example, a search of an image database returns 10 images and each image requires 3 minutes to download to the user's image display apparatus, it will take the user 30 minutes to download all of the images in order to find an image of interest. This could prove frustrating, because it is possible that many of the images could have been eliminated quickly if not for the lengthy download time.
Therefore, an efficient way to search a digital image database for the presence of a particular shape and to efficiently return a preliminary set of search results to the user is needed but not yet available.